[SHOI2016]-成绩比较

首先发现恰好 K 名碾压的好难算啊！计数题嘛，想到容斥，f 恰好，g 至少，套路一波。

$$g(k) = C^{k}_{n - 1} \times ( \prod_{i = 1}^m C^{n - r_i - k}_{n - k - 1} \sum\limits_{j = 1}^{U_i} j^{n - r_i} (U_i - j)^{r_i - 1} )$$

发现很有希望，但是后面那个 sigma 不太好搞，考虑拿出来预处理，运用二项式定理得

$$\sum\limits_{l = 0}^{r_i - 1} C_{r_i - 1}^l (-1)^l U_i^{r_i - 1 - l} \sum\limits_{j = 1}^{U_i} j^{n - r_i + l}$$

后面那个 sigma 是个自然数幂求和，用拉格朗日插值法求，然而我不会所以咕咕